import collections
import heapq


class solution1:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] < i - k + 1:
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans

class solution2:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        q = collections.deque()
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
        ans = [0] * (n - k + 1)
        ans[0] = nums[q[0]]
        for i in range(k, n):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            while q and q[0] < i - k + 1:
                q.popleft()
            ans[i - k + 1] = nums[q[0]]
        return ans
